/*
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n行，每行包含若干整数，其中第 i行表示数字三角形第 i层包含的整数。

输出格式
输出一个整数，表示最大的路径数字和。

数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000

输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例：
30
 */

//import java.util.*;
//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[][] dp = new int[n + 2][n + 2];
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= i; j++) {
//                dp[i][j] = sc.nextInt();
//                dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
//            }
//        }
//        int res = Arrays.stream(dp[n]).max().getAsInt();
//        System.out.println(res);
//    }
//}


/// /一维数组优化版本
//import java.util.*;
//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] dp = new int[n + 1]; // 使用一维数组代替二维数组
//        for (int i = 1; i <= n; i++) {
//            // 从右向左更新，避免覆盖需要使用的数据
//            for (int j = i; j >= 1; j--) {
//                dp[j] = Math.max(dp[j - 1], dp[j]) + sc.nextInt();
//            }
//        }
//        // 找到最后一层的最大值
//        int res = 0;
//        for (int i = 1; i <= n; i++) {
//            res = Math.max(res, dp[i]);
//        }
//        System.out.println(res);
//    }
//}

/*
最长上升子序列
给定一个长度为 N的数列，求数值 严格单调递增的子序列 的长度最长是多少。

输入格式
第一行包含整数 N。
第二行包含 N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−10^9≤数列中的数≤10^9

输入样例：
7
3 1 2 1 8 5 6

输出样例：
4
 */

//import java.util.*;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] arr = new int[n + 1];
//        int[] dp = new int[n + 1];
//        for (int i = 1; i <= n; i++) {
//            arr[i] = sc.nextInt();
//        }
//        for (int i = 1; i <= n; i++) {
//            int maxVal = 0;
//            for (int j = 1; j < i; j++) {
//                if (arr[i] > arr[j]) {
//                    maxVal = Math.max(maxVal, dp[j]);
//                }
//            }
//            dp[i] = maxVal + 1;
//        }
//        int res = Arrays.stream(dp).max().getAsInt();
//        System.out.println(res);
//    }
//}

/*
最长上升子序列II
给定一个长度为 N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 N。
第二行包含 N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤100000，
−10^9≤数列中的数≤10^9

输入样例：
7
3 1 2 1 8 5 6

输出样例：
4
 */

//import java.util.*;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int[] arr = new int[n + 1];
//        int len = 0;
//        int[] q = new int[n + 1];
//        for (int i = 0; i < n; i++) {
//            arr[i] = sc.nextInt();
//        }
//        q[0] = (int) -1e9 - 10;
//        for (int i = 0; i < n; i++) {
//            int left = 0, right = len;
//            while (left < right) {
//                int mid = (left + right + 1) / 2;
//                if (q[mid] < arr[i]) left = mid;
//                else right = mid - 1;
//            }
//            len = Math.max(len, left + 1);
//            q[left + 1] = arr[i];
//        }
//        System.out.println(len);
//    }
//}

/*
最长公共子串
给定两个长度分别为 N和 M的字符串 A和 B，求既是 A 的子序列又是B的子序列的字符串长度最长是多少。

输入格式
第一行包含两个整数 N和M。
第二行包含一个长度为 N的字符串，表示字符串 A。
第三行包含一个长度为 M的字符串，表示字符串 B。
字符串均由小写字母构成。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N,M≤1000

输入样例：
4 5
acbd
abedc

输出样例：
3
 */

//import java.util.*;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        int m = sc.nextInt();
//        String a = " " + sc.next();
//        String b = " " + sc.next();
//        int[][] dp = new int[1010][1010];
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++) {
//                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
//                if (a.charAt(i) == b.charAt(j)) {
//                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
//                }
//            }
//        }
//        System.out.println(dp[n][m]);
//    }
//}

/*
给定两个字符串 A和 B，现在要将A经过若干操作变为 B，可进行的操作有：
删除–将字符串 A 中的某个字符删除。
插入–在字符串 A的某个位置插入某个字符。
替换–将字符串 A中的某个字符替换为另一个字符。
现在请你求出，将 A变为 B至少需要进行多少次操作。

输入格式
第一行包含整数 n，表示字符串 A的长度。
第二行包含一个长度为 n 的字符串 A。
第三行包含整数 m，表示字符串 B的长度。
第四行包含一个长度为 m的字符串 B。
字符串中均只包含大小写字母。

输出格式
输出一个整数，表示最少操作次数。

数据范围
1≤n,m≤1000

输入样例：
10
AGTCTGACGC
11
AGTAAGTAGGC

输出样例：
4
 */

//import java.util.*;
//
//public class Main {
//    static int editDistance(String a, String b) {
//        int n = a.length() - 1;
//        int m = b.length() - 1;
//        int[][] dp = new int[1010][1010];
//        for (int i = 0; i <= m; i++) {
//            dp[0][i] = i;
//        }
//        for (int i = 0; i <= n; i++) {
//            dp[i][0] = i;
//        }
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++) {
//                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
//                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + (a.charAt(i) == b.charAt(j) ? 0 : 1));
//            }
//        }
//        return dp[n][m];
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        String a = " " + sc.next();
//        int m = sc.nextInt();
//        String b = " " + sc.next();
//        System.out.println(editDistance(a, b));
//    }
//}

/*
编辑距离
给定 n个长度不超过 10 的字符串以及 m次询问，每次询问给出一个字符串和一个操作次数上限。
对于每次询问，请你求出给定的 n个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。

输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含一个字符串，表示给定的字符串。
再接下来 m行，每行包含一个字符串和一个整数，表示一次询问。
字符串中只包含小写字母，且长度均不超过 10。

输出格式
输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。

数据范围
1≤n,m≤1000

输入样例：
3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：
1
3
 */

import java.util.*;

public class Main {
    static int editDistance(String a, String b) {
        int n = a.length() - 1;
        int m = b.length() - 1;
        int[][] dp = new int[1010][1010];
        for (int i = 0; i <= m; i++) {
            dp[0][i] = i;
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + (a.charAt(i) == b.charAt(j) ? 0 : 1));
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = " " + sc.next();
        }
        while (m-- > 0) {
            String query = " " + sc.next();
            int upperBound = sc.nextInt();
            int res = 0;
            for (int i = 0; i < n; i++) {
                if (editDistance(strs[i], query) <= upperBound) {
                    res++;
                }
            }
            System.out.println(res);
        }

    }
}